/**
 * FileName: answer_1
 * Author:   why
 * Date:     2019/3/13 11:39
 * Description:
 */
package algorithm.leetcode.problem_20;

import java.util.HashMap;
import java.util.Map;
import java.util.Stack;

public class answer_1 {
    public boolean isValid(String s) {
        Map<Character,Character> mp = new HashMap<>();
        mp.put(')','(');
        mp.put(']','[');
        mp.put('}','{');
        Stack<Character> stack = new Stack<>();
        for (int i = 0; i < s.length() ; i++) {
            char c = s.charAt(i);
            if (mp.containsKey(c)){
                char emp = stack.isEmpty() ? '#' : stack.pop();

                if (emp != mp.get(c)) {
                    return false;
                }
            } else {
                stack.push(c);
            }
        }

        return stack.isEmpty();
    }
}
